public class Leetcode799 {
    public static void main(String[] args) {
//        System.out.println(champagneTower(25, 6, 1));
        System.out.println(champagneTower(2, 1, 1));
    }

    public static double champagneTower(int poured, int queryRow, int queryGlass) {
        int maxRow = (int) Math.log(poured + 1);
        int surplusPoured = poured - 1 << maxRow - 1;
        if (maxRow >= queryRow + 1) {
            return 1;
        }

        double[] row = {poured};
        for (int i = 0; i < queryRow; i++) {
            double[] children = new double[row.length + 1];
            for (int j = 0; j < row.length; j++) {
                if (row[j] > 1) {
                    double next = row[j] - 1;
                    children[j] += next / 2;
                    children[j + 1] += next / 2;
                }
            }
            row = children;
        }

        return row[queryGlass] > 1 ? 1 : row[queryGlass];
    }

}
